package com.tal.pad.javabase.arith;

import java.util.Random;

public class BaseTest {

    public static void main(String[] args) {
        int[] arr = generArr(100, 100);
        printArr(arr);
//        selectionSort(arr);
//        bubbleSort(arr);
//        insertSort(arr);
        shellSort(arr);

        printArr(arr);

    }

    private static void insertSort(int[] arr) {
        for(int i = 1; i<arr.length; i++){
            for(int j = i; j>0; j--){
                if(arr[j]<arr[j-1]){
                    swap(arr, j, j-1);
                }
            }
        }
    }

    private static void selectionSort(int[] arr) {
        for(int i = 0 ; i<arr.length-1; i++){
            int minPos = i;
            for(int j = i; j<arr.length; j++){
                if(arr[j]<arr[minPos]){
                    minPos  =j;
                }
            }
            if(minPos!=i){
                swap(arr,minPos,i);
            }
        }
    }

    private static void shellSort(int[] arr) {
        int gap = 1;
        while(gap< arr.length/3){
            gap = gap*3+1;
        }
        System.out.println("gap:" + gap);
        for(int h = gap ; h>=1; h = (h-1)/3){
            System.out.println("gap:" + gap + " h : "+ h );
            for(int i = h ; i<arr.length; i++){
                for(int j = i; j>0; j = j-gap){
                    if(arr[j]<arr[j-gap]){
                        swap(arr,j, j-gap);
                    }
                }
            }
        }
    }

    private static void bubbleSort(int[] generedArr) {
        for(int i = generedArr.length-1; i>0; i --){
            for( int j = 0; j<i; j ++){
                if(generedArr[j]>generedArr[j+1]){
                    swap(generedArr,j, j+1);
                }
            }
        }
    }

    private static void printArr(int[] generedArr) {
        System.out.println();
        if(generedArr==null || generedArr.length<1) return;
        for (int j : generedArr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    private static int[] generArr(int length, int scrop) {
        int [] arr = new int[length];
        Random random = new Random();
        for(int i = 0 ; i<arr.length; i++){
            arr[i] = random.nextInt(scrop);
        }
        return arr;
    }

    private static void swap(int [] arr, int left , int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}
